/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-06-15
 * Time: 17:29
 */

import java.util.Scanner;

public class OptimalBST {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入键的个数
        System.out.print("请输入关键字数量 n：");
        int n = sc.nextInt();

        double[] p = new double[n + 1]; // p[1..n]
        double[] q = new double[n + 1]; // q[0..n]

        System.out.println("请输入 " + n + " 个关键字的查找概率 p[1..n]：");
        for (int i = 1; i <= n; i++) {
            System.out.print("p[" + i + "] = ");
            p[i] = sc.nextDouble();
        }

        System.out.println("请输入 " + (n + 1) + " 个虚节点的查找概率 q[0..n]：");
        for (int i = 0; i <= n; i++) {
            System.out.print("q[" + i + "] = ");
            q[i] = sc.nextDouble();
        }

        // 初始化DP表
        double[][] e = new double[n + 2][n + 1];
        double[][] w = new double[n + 2][n + 1];
        int[][] root = new int[n + 1][n + 1];

        for (int i = 1; i <= n + 1; i++) {
            e[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];
        }

        // 动态规划填表
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                e[i][j] = Double.MAX_VALUE;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int r = i; r <= j; r++) {
                    double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    if (t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = r;
                    }
                }
            }
        }

        // 输出结果
        System.out.println("\n最小期望查找代价：" + e[1][n]);
        System.out.println("根节点结构如下（区间对应的根）：");
        printRoot(root, 1, n);
    }

    static void printRoot(int[][] root, int i, int j) {
        if (i > j) return;
        System.out.println("区间 [" + i + ", " + j + "] 的根是：" + root[i][j]);
        printRoot(root, i, root[i][j] - 1);
        printRoot(root, root[i][j] + 1, j);
    }
}
